Modern data processing systems are increasingly required to store great quantities of data in the main store, which must thus be readily accessible. As high-speed and large-scale storages are very expensive, the tendency is to design storage hierarchies with different actuality levels, whose average speed corresponds to that of a high-speed, expensive storage. It is known in this connection to provide a high-speed, small-scale buffer store between the main store of the system and the processor. The cycle time for the main store, which in this case may also be referred to as a back-up store, is, for example 1 to 5 microseconds and for the high-speed buffer store 300 ns. Thus for the complete hierarchy an access time is obtained which is slightly above the cycle time of the high-speed buffer store but considerably below that of the main store.
However, the use of a high-speed buffer store gives rise to a number of problems which are essentially connected with the choice of suitable parameters, such as buffer size, associativity, replacement strategy, etc. Associativity in this connection refers to the way in which main store locations can be mapped onto buffer store locations. Generally, for example, provisions may be made for a main store data area to be storable everywhere in the buffer store, thus ensuring full associativity. However, in order to locate the data area in the buffer store, a buffer address array has to be provided which indicates the respective buffer store location for each data area or partition. It is clear that this buffer address array becomes very extensive in this general case and necessitates complicated control devices. The system is rendered simpler when a particular data area can be stored only within given geometrical boundaries of the buffer store. Such limited associativity considerably facilitates the addressing of the buffer address array and the job of determining whether a particular data area is available in the buffer store at a given time.
As buffer stores by their very nature are such that they can accommodate only a part of the main store data, it is frequently necessary to remove an old area from the buffer store before a new data area or partition can be stored. The choice of the old area is made by means of a replacement array which as a function of the given associativity indicates an area suitable for replacement. The area is replaced in accordance with different algorithms, of which the FIFO (First In First Out) algorithm and the LRU (Least Recently Used) algorithm are those most commonly known. From the various data areas to be considered the FIFO alogrithm chooses that area which was the first to be read into the buffer store, whereas the LRU algorithm selects the least recently used area.
It stands to reason that not so much the small-scale, high-speed buffer store as the control means necessary for its use, such as the buffer address array, the replacement array, and the update logic for the replacement array, involve considerable expenditure. Apart from the hardware cost, each addressing of the buffer store necessitates an addressing of the control means, which may be very time-consuming.
However, not only the user data and macro instructions but also the micro instructions of a microprogrammed data processing system, which are on the increase, call for larger micro instruction control stores. As the cost of more recent data processing have been increasingly software influenced, the tendency is to replace pure software elements by microprogram functions. In connection with virtually addressed storage hierarchies, the elements concerned may be related to storage management, multiprocessing aspects connected with jobs to be handled, source allocation, etc. The reasons for this switch from software to hardware may be summarized as follows:
greater effectiveness, since the problems to be solved are more hardware related, PA1 greater flexibility within a compatible series of computers, in that elements enhancing the efficiency of the system are hardware implemented, PA1 greater ease of use as a result of a greater number of automatisms, and PA1 simpler and thus more reliable operating system.
However, such a switch may increase the size of the microprogram to 1 megabyte. It is obvious that microprograms of that size can no longer be kept readily accessible in a high-speed storage. Whereas previously, for speed reasons, the micro instructions were stored in read-only stores, large-scale microprograms necessitate a different approach. Attempts have also been made (see, for example, U.S. Pat. No. 3,478,322) to store the the microprogram in writable stores. Megabyte microprograms necessitate, however, the use of a storage hierarchy. Such a hierarchy is known, for example, from U.S. Pat. No. 3,800,291 commonly owned by the assignee of the subject application. But also in this patent the use of a high-speed buffer store for micro instructions involves the disadvantages described above in conjunction with a buffer store employed for user data. The optimum buffer size, the associativity, etc. are difficult to determine, and the control means required (buffer address array, replacement array, control logic) constitute a substantial cost factor. Apart from this, the optimum buffer store parameters cannot be determined when the system is designed, since they are governed to a considerable degree by the application to which the system is put by the user.
The cost of the control means for different buffer stores is furthermore increased substantially by data processing systems designed as multiprocessing systems, since in such a case each processor requires separate control means and the control means as such are rendered complicated by the multiprocessor operation and the data actuality this entails in each of the buffer stores.
In spite of the obviously increased expenditure, user data and macro instructions on the one hand and micro instructions on the other were previously transferred to the processor along strictly separated paths. The reason for this was that the two types of data concern two entirely different types of information. To transfer the two types of information, buses are provided which are different with regard to the quantity of data to be transferred and the transfer speed.
Whereas the difference between user data and micro instructions is obvious, the difference between macro instructions on the one hand and micro instructions on the other will be described in detail below. Macro instructions and data are stored jointly essentially because modern data processing systems necessitate that they be handled in the same manner. This means more specifically that it must be possible for such instructions and data to be processed and modified in the same manner, thus rendering the execution of the programs and program branches, if any, flexible. However, in the case of the micro instructions conditions are entirely different. As micro instructions constitute a so-called interpreting code, the application of the Neumann principle described above, i.e., the joint storage of data and macro instructions in the main store and the instruction modifications, would not facilitate the programming techniques employed. Therefore, most data processing systems comprise different storages for macro instructions and data on the one hand and micro instructions on the other. If for cost reasons joint storage is provided for, such a storage contains two logically separated address spaces for the two different types of information (see, for example, IBM TDB May 1973, page 3799).
Thus the solutions described above for making great numbers of microprograms readily accessible are unsatisfactory because of the high cost involved. This high cost is essentially attributable to the requirement of having to provide two separate transfer paths for transferring the two types of information to the processor. Although such separate paths are in many cases advantageous from the time standpoint, since both paths can be used simultaneously, the double expenditure and in the case of multiprocessors the more than double expenditure becomes unacceptable for small and medium scale data processing systems.